package leetcode;

/**
 * @author 美女
 * @date 2022/03/28 17:54
 **/

/**
 * 定义一个函数s，统计s中（按字典序比较）最小字母的出现频次，其中s是一个非空字符串
 * 例如，若s="dcce"，那么f(s)=2，因为字典序最小字母是"c"，它出现了2次
 * 现在，给你两个字符串数组待查表queries和词汇表words。对于每次查询queries[i]
 * 需统计words中满足f(queries[i])< f(W)的词的数目，W表示词汇表words中的每个词
 * 请你返回一个整数数组answer作为答案，其中每个answer[i]是第i次查询的结果
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 分析：
 * 1.核心操作：求字符串中最小字母出现频次
 * 2.queries每个字符串都需要和words中所有字符串比较，将words字符串存储在Map集合中遍历queries[i]比较与Map中的每个words[i]比较
 */


public class Num1170_SmallFrequency {
    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        //返回的数组
        int[] array=new int[queries.length];
        Map<String,Integer> map=new HashMap<>();
        //words中的字符串及对应次数存入Map集合
        for (int i = 0; i < words.length; i++) {
            //求words[i]中最小单词对应次数
            int count=findMinCount(words[i]);
            map.put(words[i],count);
        }
        for (int i = 0; i < queries.length; i++) {
            //求queries[i]中最小单词对应次数
            int q=findMinCount(queries[i]);
            //记录q<words多少次
            int res=0;
            //两者比较
            for (int j = 0; j < words.length; j++) {
                if(q<map.get(words[j])){
                    res++;
                }
            }
            array[i]=res;
        }
        return array;
    }

    /**
     * 求字符串中最小字母出现频次
     * 边遍历边求解，先认为第一个字母就是最小字母,如果字母相等，频次++；小于min,字母替换频次归一；大于min不做处理
     * @param word
     * @return
     */
    private static int findMinCount(String word) {
        char min=word.charAt(0);
        int len=word.length();
        //记录频次
        int count=1;
        for (int i = 1; i < len ; i++) {
            if(min>word.charAt(i)){
                min=word.charAt(i);
                count=1;
            }else if(min==word.charAt(i)){
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String[] a={"bbb","cc"};
        String[] b={"a","aa","aaa","aaaa"};
        int[] array=numSmallerByFrequency(a,b);
        System.out.println(Arrays.toString(array));
    }
}
